Địa danh này xuất phát từ Wat Phnom Daun Penh (hay Wat Phnom, nghĩa là "Chùa trên đồi"), xây từ năm 1373 để thờ 5 pho tượng Phật. Đồi ở đây là một gò đất nhân tạo, đắp cao 27 m. Tên quả đồi lấy từ nhân vật Daun Penh (Bà Penh), tương truyền là một góa phụ giàu có. Phnôm Pênh còn có nghĩa là "vùng đất của Bà Pênh".

Phnôm Pênh một thời còn có tên là Krong Chaktomuk có nghĩa "Thành phố bốn mặt" do thành phố nằm trên ngã tư của mấy con sông Mekong, Bassac, sông Tonle Sap chạy ngang tạo thành bốn ngả sông. Krong Chaktomuk còn là cách gọi tắt sắc phong vua Ponhea Yat đặt cho thị trấn này là "Chaktomuk Mongkol Sakal Kampuchea Thipadei Sereythor Inthabot Borei Roth Reach Seima Maha Nokor".